从Chrome源码看JS Array的实现

1. JS Array的实现#

先看源码注释：

1
// The JSArray describes JavaScript Arrays
2
//  Such an array can be in one of two modes:
3
//    - fast, backing storage is a FixedArray and length <= elements.length();
4
//       Please note: push and pop can be used to grow and shrink the array.
5
//    - slow, backing storage is a HashTable with numbers as keys.
6
class JSArray: public JSObject {
7
  public:
8
  // [length]: The length property.
9
  DECL_ACCESSORS (length, Object)
10

11
  // Number of element slots to pre-allocate for an empty array.
12
  static const int kPreallocatedArrayElements = 4;
13
};

• 这里说明一下，如果不熟悉C/C++的，那把它成伪码就好了。

• 源码里面说了，JSArray有两种模式，一种是快速的，一种是慢速的，快速的用的是索引直接定位，慢速的使用用哈希查找，由于JSArray是继承于JSObject，所以它也是同样的处理方式，如下面的：

  1
  var ary = [1, 2, 3]
  2
  ary[2000] = 5

  • 增加一个2000的索引时，array就会被转成慢元素。

2. Push和扩容#

数组初始化大小为4：

1
// Number of element slots to pre-allocate for an empty array.
2
static const int kPreallocatedArrayElements = 4;

• 执行push的时候会在数组的末尾添加新的元素，而一旦空间不足时，将进行扩容。

• 在源码里面push是用汇编实现的，在C++里面嵌入的汇编。这个应该是考虑到push是一个最为常用的操作，所以用汇编实现提高执行速度。在汇编的上面封装了一层，用C++调的封装的汇编的函数，在编译组装的时候，将把这些C++代码转成汇编代码。

• 计算新容量的函数：

  1
  Node* CodeStubAssembler::CalculateNewElementsCapacity(Node* old_capacity, ParameterMode mode) {
  2
    Node* half_old_capacity = WordOrSmiShr(old_capacity, 1, mode);
  3
    Node* new_capacity = IntPtrOrSmiAdd(half_old_capacity, old_capacity, mode);
  4
    Node* padding = IntPtrOrSmiConstant(16, mode);
  5
    return IntPtrOrSmiAdd(new_capacity, padding, mode);
  6
  }

  • 如上代码新容量等于 ：

    1
    new_capacity = old_capacity / 2 + old_capacity + 16

    • 即老的容量的1.5倍加上16。初始化为4个，当push第5个的时候，容量将会变成：

    1
    new_capacity = 4 / 2 + 4 + 16 = 22

    • 接着申请一块这么大的内存，把老的数据拷过去：

      1
      Node* CodeStubAssembler::GrowElementsCapacity(Node* object, Node* elements, Node* capacity, Node* new_capacity) {
      2
        // Allocate the new backing store.
      3
        Node* new_elements = AllocateFixedArray(new_capacity, mode);
      4
      
      5
        // Copy the elements from the old elements store to the new.
      6
        CopyFixedArrayElements(elements, new_elements, capacity, new_capacity);
      7
        return new_elements;
      8
      }

      • 由于复制是用的memcopy，把整一段内存空间拷贝过去，所以这个操作还是比较快的。

      • 再把新元素放到当前length的位置，再把length增加1：

        1
        StoreFixedArrayElement(elements, var_length.value());
        2
        Increment(var_length, 1, mode);

3. Pop和减容#

push是用汇编实现，而pop的逻辑是用C++写的。在执行pop的时候，第一步，获取到当前的length，用这个length - 1得到要删除的元素，然后调用setLength调整容量，最后返回删除的元素：

1
int new_length = length - 1;
2
int remove_index = remove_position == AT_START ? 0 : new_length;
3
Handle<Object> result = Subclass::GetImpl(isolate, *backing_store, remove_index);
4
Subclass::SetLengthImpl(isolate, receiver, new_length, backing_store);
5
return result;

• 我们重点看下这个减容的过程：

  1
  if (2 * length <= capacity) {
  2
    // If more than half the elements won't be used, trim the array.
  3
    isolate->heap()->RightTrimFixedArray(backing_store, capacity - length);
  4
  } else {
  5
    // Otherwise, fill the unused tail with holes.
  6
    BackingStore::cast(*backing_store)->FillWithHoles(length, old_length);
  7
  }

  • 如果容量大于等于length的2倍，则进行容量调整，否则用holes对象填充。第三行的rightTrim函数，会算出需要释放的空间大小，并做标记，并等待GC回收：

  1
  int bytes_to_trim = elements_to_trim * element_size;
  2
  // Calculate location of new array end.
  3
  Address old_end = object->address() + object->Size();
  4
  Address new_end = old_end - bytes_to_trim;
  5
  CreateFillerObjectAt(new_end, bytes_to_trim, ClearRecordedSlots::kYes);

  • 也就是说，当数组的元素个数小于容量的一半时，就会进行减少的操作，将容量调整为实际的大小。

4. shift和splice数组中间的操作#

push和pop都是在数组末尾操作，相对比较简单，而shfit、unshfit、splice是在数组的开始或者中间进行操纵。我们来看一下，如果是这种情况的又是如何调整数组元素的。

5. Join和Sort#

它们是用JS实现的，然后再用wasm打包成native code。不过，join的实现逻辑并不简单，因为array的元素本身具有多样化，可能为慢元素或者快元素，还可能带有循环引用，对于慢元素，需要先排下序：

1
var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, length));

• 预处理完之后，最后创建一个字符串数组，用连接符连起来：

  1
  // Construct an array for the elements.
  2
  var elements = new InternalArray(length);
  3
  for (var i = 0; i < length; i++) {
  4
    elements[i] = ConvertToString(use_locale, array[i]);
  5
  }
  6
  
  7
  if (separator === '') {
  8
    return %StringBuilderConcat(elements, length, '');
  9
  } else {
  10
    return %StringBuilderJoin(elements, length, separator);
  11
  }

• 而sort函数是用的快速排序：

  1
  function ArraySort(comparefn) {
  2
    CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");
  3
    %Log("js/array.js execute ArraySort");  //手动添加的log打印，确保执行的是这里
  4
  
  5
    var array = TO_OBJECT(this);
  6
    var length = TO_LENGTH(array.length);
  7
    return InnerArraySort(array, length, comparefn);
  8
  }

  • 当数组元素的个数不超过10个时，是用的插入排序：

    1
    function InnerArraySort(array, length, comparefn) {
    2
      // In-place QuickSort algorithm.
    3
      // For short (length <= 10) arrays, insertion sort is used for efficiency.
    4
      function QuickSort(a, from, to) {
    5
        var third_index = 0;
    6
        while (true) {
    7
          // Insertion sort is faster for short arrays.
    8
          if (to - from <= 10) {
    9
            InsertionSort(a, from, to);
    10
            return;
    11
          }
    12
          //other code ...
    13
        }
    14
      }
    15
    }

    展开收起

  • 快速排序算法里面有一个比较重要的地方是选择枢纽元素，最简单的是每次都是选取第一个元素，或者中间的元素，在源码里面是这样选择的：

    1
    if (to - from > 1000) {
    2
      third_index = GetThirdIndex(a, from, to);
    3
    } else {
    4
      third_index = from + ((to - from) >> 1);
    5
    }

    • 如果元素个数在1000以内，则使用它们的中间元素，否则要算一下， 这个算法比较有趣：

      1
      function GetThirdIndex(a, from, to) {
      2
        var t_array = new InternalArray();
      3
        // Use both 'from' and 'to' to determine the pivot candidates.
      4
        var increment = 200 + ((to - from) & 15);
      5
        var j = 0;
      6
        from += 1;
      7
        to -= 1;
      8
        for (var i = from; i < to; i += increment) {
      9
          t_array[j] = [i, a[i]];
      10
          j++;
      11
        }
      12
        t_array.sort(function(a, b) {
      13
          return comparefn(a[1], b[1]);
      14
        });
      15
        var third_index = t_array[t_array.length >> 1][0];
      16
        return third_index;
      17
      }

      展开收起
      • 先取一个递增间距200~215之间，再循环取出原元素里面落到这个间距的元素，放到一个新的数组里面（这个数组是C++里面的数组），然后排下序，取中间的元素。因为枢纽元素的刚好是所有元素的中位数时，排序的效果最好，而这里是取出少数元素的中位数，类似于抽样模拟，缺点是它得再借助另外的排序算法。
      • 最后再比较一下Array和线性链接的速度。

Array和线性链接的速度#

线性链接是一种非连续存储的数据结构，每个元素都有一个指针指向它的下一个元素，所以它删除元素的时候不需要移动其它元素，也不需要考虑扩容的事情，但是它的查找比较慢。我们实现一个简单的List和Array进行比较。

• List的每个节点用一个Node表示：

  1
  class Node{
  2
    constructor(value, next){
  3
        this.value = value;
  4
        this.next = next;
  5
    }
  6
  }

• 每个List都有一个头指针指向第一个元素，和一个length记录它的长度：

  1
  class List{
  2
    constructor(){
  3
        this.head = null;
  4
        this.tail = null;
  5
        this.length = 0;
  6
    }
  7
  }

• 然后实现它的push和unshift函数：

  1
  class List{
  2
    unshift(value){
  3
        return this.insert(0, value);
  4
    }
  5
    push(value){
  6
        if(this.head === null){
  7
            this.head = new Node(value, this.tail);
  8
            this.length++;
  9
        } else {
  10
            this.insert(this.length, value);
  11
        }
  12
        return this.length;
  13
    }
  14
  }

• 两个函数都会调一个通用的insert函数：

  1
  insert(index, value){
  2
    var insertPos = this.head;
  3
    //找到需要插入的位置的节点
  4
    for(var i = 0; i < index - 1; i++){
  5
        insertPos = insertPos.next;
  6
    }
  7
    var node = null;
  8
    if(index === 0){
  9
        node = new Node(value, this.head);
  10
        this.head = node;
  11
    } else {
  12
        node = new Node(value, insertPos.next);
  13
        insertPos.next = node;
  14
    }
  15
    this.length++;
  16
    return value;
  17
  }

  展开收起

• 有了这个List之后，就可以初始化一个list和array：

  1
  var list = new List();
  2
  var arr = [];
  3
  for(var i = 0; i < 100; i++){
  4
      list.push(i);
  5
      arr.push(i);
  6
  }

• 然后用下面的代码比较List和Array在数组起始位置插入元素的操作时间：

  1
  var count = 10000;
  2
  console.time("list unshfit");
  3
  for(var i = 0; i < count; i++){
  4
      list.unshift(i);
  5
  }
  6
  console.timeEnd("list unshfit");
  7
  
  8
  console.time("array unshfit");
  9
  for(var i = 0; i < count; i++){
  10
      arr.unshift(i);
  11
  }
  12
  console.timeEnd("array unshfit");

• 再比较从正中间位置插入元素的时间：

  1
  console.time("list insert middle with index");
  2
  for(var i = 0; i < count; i++){
  3
      insertPos = list.insert(list.length >> 1, i);
  4
  }
  5
  console.timeEnd("list insert middle with index");
  6
  
  7
  console.time("array insert middle");
  8
  for(var i = 0; i < count; i++){
  9
      arr.splice(arr.length >> 1, 0, i);
  10
  }
  11
  console.timeEnd("array insert middle");

  • 运行可以得到以下表格：

    	unshift	splice(n/2)
    Array	350ms	7.99ms
    List	8.23ms	106ms

    • 可以看到在队首插入元素，使用线性链接List的时间将会数量级的优于Array。如果是在中间位置插入的话，由于 List的查找花费了很多时间，导致总时间明显高于Array。但是如果在插入的时候，记住上一次的位置，那么List又会明显快于Array。如下换成记录插入的位置：

      1
      console.time("list insert middle with pos");
      2
      var insertPos = list.getNode(list.length >> 1);
      3
      for(var i = 0; i < count; i++){
      4
          insertPos = list.insertFromNode(insertPos, i);
      5
      }
      6
      console.timeEnd("list insert middle with pos");

      • 时间比较List又快于Array：

        	unshift	splice(n/2)	splice pos
        Array	350ms	7.99ms	8.07ms
        List	8.23ms	106ms	1.78ms

• 综上，Array的实现用了三种语言：汇编、C++和JS，最常用的如push用了汇编实现，比较常用的如pop/splice等用了C++，较为少用的如join/sort用了JS。

• Array为快元素即普通的数组时，增删元素操作需要不断的扩容、减容和调整元素的位置。特别是当不断地在起始位置插入元素时，和链表相比，这种时间效率还是比较低下的。如果使用的场景是要根据index删除元素，使用Array还是有优势，但是若能够很快定位到删除元素的位置，链表毫无疑问是更合适的。

• 【转载】原文地址：https://zhuanlan.zhihu.com/p/26388217?utm_source=weibo&utm_medium=social